/**
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 * 二叉树的直径(一棵二叉树的直径长度是任意两个结点路径长度中的最大值, 其实就是左右子树深度之和)
 * @param root 
 */
const diameterOfBinaryTree = (root: TreeNode | null): number => {
    let ans = 0
    /**
     * 获取节点n的左右子树深度
     * @param n 
     */
    const getBothDepth = (n: TreeNode | null): number => {
        if (n === null) return 0

        // 左子树的深度
        const leftDepth = getBothDepth(n.left)

        // 右子树的深度
        const rightDepth = getBothDepth(n.right);
        
        // 更新直径
        ans = Math.max(leftDepth + rightDepth, ans)
        return Math.max(leftDepth, rightDepth) + 1
    }
    getBothDepth(root)

    return ans
};